/*
   @Copyright:LeetCode
   @Author:   tjyemail
   @Problem:  http://leetcode.com/problems/clone-graph
   @Language: C++
   @Datetime: 19-11-18 10:12
   */

/*
// Definition for a Node.
class Node {
public:
	int val;
	vector<Node*> neighbors;

	Node() {}

	Node(int _val, vector<Node*> _neighbors) {
		val = _val;
		neighbors = _neighbors;
	}
};
*/

class Solution {
	unordered_map<Node*,Node*> dict;
public:
	Node* cloneGraph(Node* node) {
		if(node==NULL) return NULL;
		if(dict.count(node)) return dict[node];
		Node *copy = dict[node] = new Node(node->val, vector<Node*>());
		for(const auto &n:node->neighbors)
			copy->neighbors.push_back(cloneGraph(n));
		return copy;
	}
};
